package com.javabasic.algorithm.leetcode;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/25 10:03 下午
 * @see [leetcode 240](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
 */
public class SearchA2DMatrixII {

    /**
     * 解法一：DFS
     * 增加这两个变量的目的主要就是为了加快剪枝
     * dp数组的目的是为了防止统一个位置重复计算
     */
    boolean result;
    boolean[][] dp;
    public boolean searchMatrix(int[][] matrix, int target) {
        int raw = matrix.length - 1;
        int col = matrix[0].length - 1;
        dp = new boolean[raw+1][col+1];
        int currentRaw = 0, currentCol = 0;
        result = false;
        search(matrix, raw, col, currentRaw, currentCol, target);
        dp[currentRaw][currentCol] = true;
        return  result;
    }

    private void search(int[][] matrix, int raw, int col, int currentRaw, int currentCol, int target) {
        if (result || currentRaw > raw || currentCol > col || dp[currentRaw][currentCol] || matrix[currentRaw][currentCol] > target) {
            return;
        }
        if (matrix[currentRaw][currentCol] == target) {
            result = true;
            return;
        }
        search(matrix,raw,col,currentRaw+1, currentCol, target);
        if (currentRaw < raw) {
            dp[currentRaw+1][currentCol] = true;
        }
        search(matrix,raw,col,currentRaw, currentCol+1, target);
        if (currentCol < col) {
            dp[currentRaw][currentCol + 1] = true;
        }
    }


    /**
     * 解法二：从右上角看，将矩阵看作为一个类似二叉搜索树的结构
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        int rawLen = matrix.length;
        int raw = 0;
        int col = matrix[0].length - 1;
        while (raw < rawLen && col >= 0) {
            if (matrix[raw][col] == target) return true;
            else if (matrix[raw][col] > target) col--;
            else raw++;
        }
        return false;
    }
}
